import java.util.Stack;

/*
 * @author zzr
 * @date: 2025/10/14  11:16
 * @description: 有效的括号。给定一个字符串 （）{}[] 判断字符串是否有效
 * 1. 左括号必须用相同类型对应的右括号闭合
 * 2. 左括号必须以正确的顺序闭合
 * 3. 每个右括号都有一个对应的相同类型的括号
 *
 * 1：遍历字符串，将每个括号提取出来
 * 2.因为要进行配对，所以需要分出左右
 * 3.如果为左括号，则入栈
 * 4.如果为右括号，则进行匹配
 *      匹配中，
 *          1.如果栈为空，即栈中没有左括号，直接返回 false
 *          2.栈不为空，peek 一下栈顶的左括号，判断是否能匹配
 *              能匹配的话，将左括号弹出
 *              否则发挥 false
 * 5. 当遍历完所有字符后，判断栈是否为空，如果不为空，没有全部匹配完毕，则返回 false
 */
public class Demo16 {
    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                // 左括号则入栈
                stack.push(ch);
            }  else {
                // 右括号则匹配
                // 右括号一定要按顺序与左括号进行匹配
                // 如果无左括号进行匹配 直接 false
                if (stack.isEmpty()) {
                    return false;
                }
                // 获得最近的栈顶的左括号
                char top = stack.peek();
                if ((top == '(' && ch == ')') || (top == '[' && ch == ']') || (top == '{' && ch == '}')) {
                    stack.pop(); // 匹配成功
                } else {
                    // 匹配失败
                    return false;
                }
            }
        }

        // 循环匹配完所有的字符之后
        if (!stack.isEmpty()) {
            // 仍然有括号未匹配完毕
            return false;
        }
        return true;
    }

}
